package huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {

  public static void main(String[] args) {
    int[]arr = new int[]{13,7,8,3,29,6,1};
    Node node = createHuffmanTree(arr);

    preOrder(node);
  }

  public static void preOrder(Node root){
    if (root != null){
      root.preOrder();
    }else {
      System.out.println("该树为空");
    }
  }

  public static Node createHuffmanTree(int[] arr){
    List<Node> list = new ArrayList<>();
    /*
    第一梦为了操作方便
    1.追历 arr数组
    2.将arr的每个元露构曦成一个Node
    3.将Node救入到ArrayList中
     */
    for (int value : arr) {
      list.add(new Node(value));
    }

//    从小到大
    Collections.sort(list);

    System.out.println("list:" + list);

    while (list.size() > 1){
      //    开始处理，取出最小的两个节点，并求出它俩的父节点，然后更新list
      Node left = list.get(0);
      Node right = list.get(1);
      Node parent = new Node(left.value + right.value);

      parent.left = left;
      parent.right =right;

      list.remove(left);
      list.remove(right);

      list.add(parent);

      Collections.sort(list);
    }
    return list.get(0);





  }
}

class Node implements Comparable<Node>{

  public int value;
  public Node left;
  public Node right;

//  前序遍历
  public void preOrder(){
    System.out.println(this);
    if (this.left != null){
      this.left.preOrder();
    }
    if (this.right != null){
      this.right.preOrder();
    }
  }

  public Node(int value) {
    this.value = value;
  }

  @Override
  public String toString() {
    return "Node{" +
            "value=" + value +
            '}';
  }

//  从小到大排序
  @Override
  public int compareTo(Node o) {
    return this.value - o.value;
  }
}
